#include "GobangDoc.h"
#include "match.h"
#include "calculate.h"

bool match(BoardState* src,BoardState* pattern,int srcLen,int patternLen){
	const int sLen=srcLen;
	const int pLen=patternLen;
	int mNum=0;

	int prefix[pLen];
	calculate(pattern,prefix,pLen);

	for(int i=0;i<sLen;++i){

		while(mNum>0 && pattern[mNum]!=src[i]){
			mNum=prefix[mNum-1];
		}

		if(pattern[mNum]==src[i]){
			++mNum;
		}

		if(mNum==pLen)
			return true;
	}

	return false;
}
